home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / Libraries / DCLAP 4j / DClap / DList.cpp < prev    next >
Encoding:
Text File  |  1995-12-17  |  11.1 KB  |  521 lines  |  [TEXT/R*ch]
  1. // DList.cp
  2. // This code owes it's structure in large part to Apple's MacApp UList unit
  3. // however, d.gilbert has substatially rewritten it.
  4.  
  5.  
  6. #include <ncbi.h>
  7. #include <dgg.h>
  8. #include "DList.h"
  9.  
  10.  
  11. static const short kArrayIncrement = 6;         
  12.  
  13. typedef    DObject* DObjectPtr;
  14.  
  15.  
  16. // class DArray
  17.  
  18.  
  19. DArray::DArray(short itemSize, long initialSize)
  20. {
  21.   SetClass("DArray",sizeof(DArray));
  22.     fArraySize = kEmptySize;
  23.     fArrayIncrement = kArrayIncrement;
  24.     fSize = kEmptySize;
  25.     fArrayStore = NULL;
  26.  
  27.     fItemSize = itemSize;
  28.     fItemSizeShift = 0;
  29.     if (odd(itemSize)) ++itemSize; // make sure we have even size for shifting
  30.     while (((itemSize - 1) >> fItemSizeShift) > 0) ++fItemSizeShift;
  31.     this->SetArraySize(initialSize);
  32. } 
  33.  
  34. DArray::~DArray()
  35. {
  36.     fArrayStore= MemFree(fArrayStore);
  37. }  
  38.  
  39. void DArray::DeleteAll()
  40. {
  41.     if (fSize > kEmptySize) this->DeleteItemsAt(0, fSize); //1,fSize
  42. } 
  43.  
  44. DObject* DArray::Clone()
  45. {
  46.     DArray* result = (DArray*) DObject::Clone();
  47.     result->fArrayStore= MemDup(fArrayStore,  (ulong) (fArraySize << fItemSizeShift));
  48.     return result;
  49. }
  50.  
  51. void* DArray::ComputeAddress(long index)
  52. {
  53.     return (void*) ((char*)fArrayStore + (index << fItemSizeShift)); 
  54. }  
  55.  
  56.  
  57.  
  58. void DArray::DeleteItemsAt(long index, long count)
  59. {
  60.     VoidPtr indexPtr, nextItemPtr, lastItemPtr;
  61.     long countBytes;
  62.  
  63.     countBytes = count << fItemSizeShift;
  64.     indexPtr = this->ComputeAddress(index);
  65.     nextItemPtr = this->ComputeAddress(index + count);
  66.     lastItemPtr = this->ComputeAddress(fSize); //1based: + 1);
  67.  
  68.     if (nextItemPtr < lastItemPtr)        
  69.         MemMove(indexPtr, nextItemPtr, (long)lastItemPtr - (long)nextItemPtr);
  70.  
  71.     this->SetArraySize(fSize - count);        
  72.     fSize -= count;
  73. }   
  74.  
  75.  
  76.  
  77.  
  78. void DArray::GetItemsAt(long index, void* itemPtr, long count)
  79. {
  80.     if (count > kEmptySize)
  81.         MemMove( itemPtr, this->ComputeAddress(index), 
  82.             ((count - 1) << fItemSizeShift) + fItemSize);         
  83. }  
  84.  
  85.  
  86. void DArray::ReplaceItemsAt(long index, void* itemPtr, long count)
  87. {
  88.     VoidPtr indexPtr= this->ComputeAddress(index);
  89.     long countBytes= count << fItemSizeShift;
  90.     MemMove( indexPtr, itemPtr, countBytes);
  91. } 
  92.  
  93.  
  94. void DArray::InsertItemsBefore(long index, void* itemPtr, long count)
  95. {
  96.     VoidPtr indexPtr, nextIndexPtr, lastItemPtr;
  97.     long countBytes;
  98.  
  99.     this->SetArraySize(fSize + count);                 
  100.     indexPtr = this->ComputeAddress(index);
  101.     nextIndexPtr = this->ComputeAddress(index + count);
  102.     lastItemPtr = this->ComputeAddress(fSize);    //1based: fSize + 1
  103.     countBytes = count << fItemSizeShift;
  104.  
  105.     if (index < fSize)        //1based: <=             
  106.         MemMove( nextIndexPtr, indexPtr, (long)lastItemPtr - (long)indexPtr);
  107.  
  108.     if ((countBytes == sizeof(long)) && !odd((long)itemPtr) && !odd((long)indexPtr))
  109.         *((long*)indexPtr) = *((long*)itemPtr);        // shortcut for longs 
  110.     else
  111.         MemMove(indexPtr, itemPtr, countBytes); 
  112.  
  113.     fSize += count;
  114. }  
  115.  
  116.  
  117.  
  118.  
  119. void DArray::SetArraySize(long theSize)
  120. {
  121.     long newSize;
  122.     
  123.     if ((theSize > fArraySize) || (fArraySize - theSize >= fArrayIncrement)) {
  124.         if (fArrayIncrement)
  125.             newSize = (theSize + fArrayIncrement) 
  126.                                 - (theSize + fArrayIncrement) % fArrayIncrement;
  127.         else
  128.             newSize = theSize;
  129.         if (newSize != fArraySize)  {
  130.             ulong chunk= (ulong) (newSize << fItemSizeShift);
  131.             if (fArrayStore == NULL) fArrayStore = MemNew( chunk);
  132.             else fArrayStore= MemMore(fArrayStore, chunk);
  133.             }
  134.         fArraySize = newSize;
  135.       }
  136. } 
  137.  
  138.  
  139. long DArray::Search(CompareFunc compare, void *itemPtr)
  140. {
  141.     register char*  itemAt = (char*) fArrayStore;
  142.     long     itemsize= 1 << fItemSizeShift;
  143.         
  144.         // speed this up w/ a bisection method == start in middle & bounce around ??
  145.         // NO -- can't assume this array is SORTED !!
  146. #if 0
  147.     long lo, hi, mid;
  148.     short cmp;
  149.     lo= 0; 
  150.     hi= fSize;
  151.     do {
  152.         mid= (hi+lo) >> 1;  // div 2;
  153.         itemAt= (char*) fArrayStore + mid * itemsize;
  154.         cmp= (*compare)( itemPtr, itemAt);
  155.         if (cmp == 0) return mid;
  156.         else if (cmp > 0) lo= mid;
  157.         else hi= mid;
  158.     } while (hi > lo+1);
  159.     
  160.     if (mid != hi) {
  161.         itemAt= (char*) fArrayStore + hi * itemsize;
  162.         cmp= (*compare)( itemPtr, itemAt);
  163.         if (cmp == 0) return hi;
  164.         }
  165.     else if (mid != lo) {
  166.         itemAt= (char*) fArrayStore + lo * itemsize;
  167.         cmp= (*compare)( itemPtr, itemAt);
  168.         if (cmp == 0) return lo;
  169.         }
  170.     return kEmptyIndex;
  171. #else
  172.     register long i;
  173.     for (i = 0; i < fSize; i++) {
  174.         if ( (*compare)( itemPtr, itemAt) == 0) 
  175.             return i;
  176.         itemAt += itemsize;
  177.         }
  178.     return kEmptyIndex;
  179. #endif
  180. }     
  181.  
  182.  
  183.  
  184.  
  185.  
  186.  
  187.  
  188. // class DList
  189.  
  190. // default fCompareFunc
  191. short DefaultCompare(void* item1, void* item2)
  192. {
  193.     if ((unsigned long) item1 > (unsigned long) item2)
  194.         return 1;
  195.     else if ((unsigned long) item1 < (unsigned long) item2)
  196.         return -1;
  197.     else
  198.         return 0;
  199. } 
  200.  
  201.  
  202. DList::DList(CompareFunc itsComparer, short options): 
  203.     DArray(sizeof(DObject*), kEmptySize)
  204. {
  205.   SetClass("DList",sizeof(DList));
  206.     if (itsComparer) fCompareFunc= itsComparer;
  207.     else fCompareFunc= ::DefaultCompare;
  208.     fOwnObjects= options & kOwnObjects;
  209.     fDeleteObjects = options & kDeleteObjects;        
  210. } 
  211.  
  212. DList::~DList()
  213. {
  214.     if (fDeleteObjects) this->FreeAllObjects();
  215. } 
  216.  
  217.         
  218. DObject* DList::At(long index)
  219. {
  220.     //return (*this)[index];
  221.     if (index<0 || index>=fSize) return NULL;
  222.     DObject** vp= (DObject**) ((char*)fArrayStore + (index << fItemSizeShift)); 
  223.     if (vp) return *vp;
  224.     else return NULL;
  225. } 
  226.  
  227.  
  228.  
  229. void DList::FreeAllObjects()
  230. {
  231.     long i, n= this->GetSize();
  232.     for (i= 0; i<n; i++) {
  233.         DObject* obj= At(i);
  234.         if (obj) {
  235.           if (obj->GetOwnerCount() <= 1) delete obj;
  236.           else obj->suicide(); // this alone doens't call obj destructors !!
  237.           }
  238.         }
  239.     this->DeleteAll();
  240. } 
  241.  
  242.  
  243. long DList::GetEqualItemNo(DObject* item)
  244. {
  245.     long index;
  246.  
  247.     if (item == NULL) return kEmptyIndex;
  248.     index = this->Search( fCompareFunc, &item);
  249.     return index;  // == kEmptyIndex if no match
  250. } 
  251.  
  252.  
  253.  
  254. #if 1
  255. // choose your sort
  256.  
  257. void DList::QuickSort(long beginIndex, long endIndex, CompareFunc CompareItems)
  258. // recursive qs
  259. {
  260.     long i, j;
  261.      DObjectPtr    iobj, jobj, endobj;
  262.      
  263.     if (beginIndex < endIndex) {
  264.         i = beginIndex; 
  265.         j = endIndex;  
  266.         endobj= this->At(endIndex);
  267.         do {
  268.             iobj= this->At(i);            
  269.             while (i < j && CompareItems( iobj, endobj) <= 0) 
  270.                 iobj= this->At(++i);            
  271.             jobj= this->At(j);
  272.             while (j > i && CompareItems( jobj, endobj) >= 0) 
  273.                 jobj= this->At(--j);
  274.             if (i<j) {    // swap
  275.                 this->ReplaceItemsAt(i, &jobj, 1); //was &     
  276.                 this->ReplaceItemsAt(j, &iobj, 1); //was &     
  277.                 }
  278.         } while (i < j);
  279.         
  280.          this->ReplaceItemsAt(i, &endobj, 1);  
  281.         this->ReplaceItemsAt(endIndex, &iobj, 1);  
  282.         if (i - beginIndex < endIndex - i) {
  283.             QuickSort( beginIndex, i-1, CompareItems);
  284.           QuickSort( i+1, endIndex, CompareItems);
  285.           }
  286.         else {
  287.             QuickSort( i+1, endIndex, CompareItems);
  288.              QuickSort( beginIndex, i-1, CompareItems);
  289.              }
  290.         }
  291. }
  292.  
  293. long DList::QSPartition(long beginIndex, long endIndex,     
  294.                                    CompareFunc CompareItems)
  295. {
  296.     return 0;
  297. }
  298.  
  299. long DList::QSRandomPartition(long beginIndex, long endIndex,     
  300.                                    CompareFunc CompareItems)
  301. {
  302.     return 0;
  303. }
  304.  
  305.  
  306. #else
  307. // this was Apple's algorithm
  308.  
  309. void DList::QuickSort(long beginIndex, long endIndex, CompareFunc CompareItems)
  310. {
  311.     if (beginIndex < endIndex) {
  312.         long left = this->QSRandomPartition(beginIndex, endIndex, CompareItems);
  313.         this->QuickSort(beginIndex, left, CompareItems);
  314.         this->QuickSort(left+1, endIndex, CompareItems);     
  315.     }
  316. } 
  317.  
  318.  
  319. long DList::QSPartition(long beginIndex, long endIndex, CompareFunc CompareItems)
  320. {
  321.     if (beginIndex >= endIndex)
  322.         return endIndex;
  323.     {
  324.         DObjectPtr pivot = this->At(beginIndex);                // x
  325.         long i = beginIndex - 1;    // p - 1
  326.         long j = endIndex + 1;    // r + 1
  327.         while (true)
  328.         {
  329.             DObjectPtr secondKey;
  330.             do
  331.             {
  332.                 --j;
  333.                 secondKey = this->At(j);    // A[j]
  334.             } while (CompareItems( pivot, secondKey) <= -1);
  335.             do
  336.             {
  337.                 ++i;
  338.                 secondKey = this->At(i);    // A[i]
  339.             } while (CompareItems( pivot, secondKey) >= 1);
  340.             if (i < j)
  341.             {    // Swap the Items
  342.                 DObjectPtr leftObject = this->At(i);
  343.                 DObjectPtr rightObject = this->At(j);
  344.                 this->ReplaceItemsAt(i, &rightObject, 1); // was &
  345.                 this->ReplaceItemsAt(j, &leftObject, 1); //was &
  346.             }
  347.             else
  348.                 return j;
  349.         }
  350.     }
  351. } 
  352.  
  353.  
  354. long RandomArrayIndex(long beginIndex, long endIndex)
  355. {
  356.     if (beginIndex == endIndex) return beginIndex;
  357.     //long randomValue = rand() % labs(endIndex - beginIndex);// labs() not found by g++
  358.     long randomValue = endIndex - beginIndex;
  359.     if (randomValue < 0) randomValue = -randomValue;
  360.     randomValue= rand() % randomValue;
  361.     return beginIndex + randomValue;
  362. }
  363.  
  364. long DList::QSRandomPartition(long beginIndex, long endIndex, CompareFunc CompareItems )
  365. {
  366.     long i = RandomArrayIndex(beginIndex, endIndex);
  367.     
  368.     // exchange
  369.     DObjectPtr beginIndexObject = this->At(beginIndex);
  370.     DObjectPtr ithObject = this->At(i);
  371.     this->ReplaceItemsAt(beginIndex, &ithObject, 1); //was &    // A[beginIndex] = A[i]
  372.     this->ReplaceItemsAt(i, &beginIndexObject, 1); //was &    // A[i] = A[beginIndex]
  373.  
  374.     return this->QSPartition(beginIndex, endIndex, CompareItems);
  375. } 
  376.  
  377. #endif
  378.  
  379.  
  380. void DList::Sort()
  381. {
  382.     if (this->GetSize() > 0)
  383.         this->QuickSort(0, fSize-1, fCompareFunc); // was 1,fsize
  384. } 
  385.  
  386. void DList::SortBy(CompareFunc CompareItems)
  387. {
  388.     if (this->GetSize() > 0)
  389.         this->QuickSort(0, fSize-1, CompareItems); // was 1,fsize
  390. } 
  391.  
  392.  
  393. void DList::AtDelete(long index)
  394. {
  395.     if (fDeleteObjects)  At(index)->suicide(); //delete At(index); 
  396.         // ^^ this will make a mess of Pop() and Dequeue() method results, who call here
  397.     this->DeleteItemsAt(index, 1);
  398. }
  399.  
  400. void DList::Delete(DObject* item)
  401. {
  402.     long index;
  403.     if (item == NULL) return;
  404.     index = this->GetIdentityItemNo(item);
  405.     if (index != kEmptyIndex) this->AtDelete(index);
  406. } 
  407.  
  408.  
  409. DObject* DList::First()
  410. {
  411.     if (fSize <= kEmptySize)
  412.         return NULL;
  413.     else
  414.         return this->At(0); //1based: 1
  415. } 
  416.  
  417. DObject* DList::Last()
  418. {
  419.     if (fSize <= kEmptySize)
  420.         return NULL;
  421.     else
  422.         return this->At(fSize-1);
  423. }  
  424.  
  425.  
  426. long DList::GetIdentityItemNo(DObject* item)
  427. {
  428.     if (item == NULL) return kEmptyIndex;
  429.     long i, n= this->GetSize();
  430.     for (i= 0; i<n; i++) if (At(i) == item) return i;
  431.     return kEmptyIndex; 
  432. } 
  433.  
  434.  
  435. void DList::AtPut(long index, DObject* newItem)
  436. {
  437.     if (fOwnObjects && newItem) newItem->newOwner();
  438.     this->ReplaceItemsAt( index, &newItem, 1); //was &newItem
  439. } 
  440.  
  441.  
  442. void DList::InsertBefore(long index, DObject* item)
  443. {
  444.     if (fOwnObjects && item) item->newOwner();
  445.     this->InsertItemsBefore(index, &item, 1); // was &item !!!
  446. }
  447.  
  448.  
  449. void DList::InsertInOrder(DObject* item)
  450. {
  451.     long index= Search( fCompareFunc, &item);
  452.     if (index > kEmptyIndex)
  453.         InsertBefore( index, item);
  454.     else
  455.         InsertBefore( fSize, item);
  456. } 
  457.  
  458. void DList::InsertFirst(DObject* item)
  459. {
  460.     this->InsertBefore(0, item); //1
  461. } 
  462.  
  463. void DList::InsertLast(DObject* item)
  464. {
  465.     this->InsertBefore(fSize, item); // + 1
  466. } 
  467.  
  468.  
  469. void DList::Push(DObject* item)
  470. {
  471.     this->InsertLast(item);
  472. } 
  473.  
  474. DObject* DList::Pop()
  475. {
  476.     DObject* topOfStack;
  477.  
  478.     if (fSize <= kEmptySize)
  479.         topOfStack = NULL;
  480.     else {
  481.         topOfStack = this->At(fSize-1);
  482.         //this->AtDelete(fSize-1);
  483.         this->DeleteItemsAt(fSize-1, 1);     // this bypasses fDeleteObjects check ...
  484.         }
  485.     return topOfStack;
  486. } 
  487.  
  488.  
  489.  
  490. void DList::Queue(DObject* item)
  491. {
  492.     this->InsertLast(item);
  493. } 
  494.  
  495. DObject* DList::Dequeue()
  496. {
  497.     DObject* beginningOfStack;
  498.  
  499.     if (fSize <= kEmptySize)
  500.         beginningOfStack = NULL;
  501.     else {
  502.         beginningOfStack = this->At(0);    //1based: 1
  503.         //this->AtDelete(0);                 //1based: 1
  504.         this->DeleteItemsAt(0, 1);     // this bypasses fDeleteObjects check ...
  505.         }
  506.     return beginningOfStack;
  507. } 
  508.  
  509.  
  510.  
  511.  
  512.  
  513. DList*    FreeListIfObject(DList* aList)
  514. {
  515.     if (aList) {
  516.         //aList->FreeAllObjects(); // destructor now calls FreeAllObjects()
  517.         delete aList; 
  518.         }
  519.     return NULL;
  520. }
  521.